package 排序;

import java.util.ArrayList;
import java.util.List;

import 排序.tools.Integers;

public class ShellSort<E extends Comparable<E>> extends Sort<E>{

	@Override
	protected void sort() {
		// 生成步长序列
		List<Integer> shellStepSequence = shellStepSequence();
		// 对每一个步长进行排序
		for (Integer step : shellStepSequence) {
			sort(step);
		}
	}
	
	/**
	 * 对步长为step的数组进行插入排序
	 * @param step
	 */
	private void sort(int step) {
		for (int col = 0; col < step; col++) {
			for (int begin = col + step; begin < array.length; begin += step) {
				E element = array[begin];
				int cur = begin;
				while (cur > col && cmp(element, array[cur - step]) < 0) {
					array[cur] = array[cur - step];
					cur -= step;
				}
				array[cur] = element;
			}
		}
	}
	
	/**
	 * 生成步长序列
	 * @param count
	 * @return
	 */
	private List<Integer> shellStepSequence() {
		List<Integer> stepSequence = new ArrayList<>();
		int step = array.length;
		while ((step >>= 1) > 0) {
			stepSequence.add(step); 
		}
		return stepSequence;
	}
}
